/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/copy-list-with-random-pointer
   @Language: C++
   @Datetime: 19-11-18 15:23
   */

/*
// Definition for a Node.
class Node {
public:
	int val;
	Node* next;
	Node* random;

	Node() {}

	Node(int _val, Node* _next, Node* _random) {
		val = _val;
		next = _next;
		random = _random;
	}
};
*/

class Solution {
public:
	Node* copyRandomList(Node* head) {
		for(Node* p=head; p; p=p->next->next)
			p->next = new Node(p->val, p->next, NULL);
		for(Node* p=head; p; p=p->next->next)
			if(p->random) p->next->random = p->random->next;
		Node H(-1,NULL,NULL);
		for(Node *p=head, *q=&H; p;){
			q=q->next=p->next;
			p=p->next=q->next;
		}
		return H.next;
	}
};
